The present invention relates to communications networks and to security and encryption techniques. More particularly, the present invention relates to network architectures and methods for encrypting communications data messages between clients and servers.
Modern communications often require privacy, whether for transmission of financial information in the course of electronic commerce or for transmission of trade secrets and other important commercial information. One way to protect the privacy of communications is to encrypt them according to either a symmetric cryptosystem or an asymmetric cryptosystem.
In general, a symmetric cryptosystem is a set of instructions, implemented in either hardware, software or both that can convert plaintext (the unencrypted information) to ciphertext, or vice versa, in a variety of ways, using a specific key that is known to the users but is kept secret from others. An example of a symmetric cryptosystem is the Data Encryption Standard (DES), which is described in Data Encryption Standard, Federal Information Processing Standards Publication 46 (1977) (xe2x80x9cFIPS PUB 46xe2x80x9d, republished as FIPS PUB 46-1 (1988)) and DES Modes of Operation, FIPS PUB 81 (1980) that are available from the U.S. Department of Commerce.
An asymmetric encryption system typically employs two keys, one for encryption and one for decryption, where knowledge of one key (the public key) does not permit derivation of the second key (the private key). Various aspects of public-key cryptographic (PKC) systems are described in the literature, including R. L. Rivest et al., xe2x80x9cA Method for Obtaining Digital Signatures and Public-Key Cryptosystems,xe2x80x9d Communications of the ACM vol. 21, pp. 120-126 (February 1978); M. E. Hellman, xe2x80x9cThe Mathematics of Public-Key Cryptographyxe2x80x9d, Scientific American vol. 234, no. 8, pp. 146-152, 154-157 (August 1979); and W. Diffie, xe2x80x9cThe First Ten Years of Public-Key Cryptographyxe2x80x9d, Proceedings of the IEEE vol. 76, pp. 560-577 (May 1988).
For either a symmetric or PKC system, the security of a message is dependent to a great extent on the length of the key, as described in C. E. Shannon, xe2x80x9cCommunication Theory of Secrecy Systemsxe2x80x9d, Bell System Technical Journal vol. 28, pp. 656-715 (October 1949).
Many popular PKC systems use the fact that finding large prime numbers is computationally easy but factoring the products of two large prime numbers is computationally difficult. Thus, PKC permits the user""s public key to be posted (e.g., in a directory or on a bulletin board), without compromising the user""s private key. This public-key concept simplifies the key distribution process. Example PKC algorithms are the digital signature algorithm and secure hash algorithm (DSA/SHA) and RSA/MD5.
The RSA algorithm is described in the above-cited publication by R. L. Rivest et al. and is commonly used in a client-server processor architecture, such as that illustrated in FIG. 1, to encrypt a message M using the server""s public key [e, n] resulting in ciphertext Mxe2x80x2 as follows:
Mxe2x80x2=Me mod n
This RSA encryption operation is computationally expensive for clients that currently have limited computing power, e.g., mobile phones and personal digital assistants (PDAs). As a result, the time needed for such a thin client to encrypt a message can be unacceptable.
In a client-proxy-server architecture such as that illustrated in FIG. 2, the client may be able to exploit the higher computational power of the proxy to off-load the expensive RSA encryption algorithm and reduce the client""s response time. For one example, the client can simply pass the plaintext message M to the proxy, which in turn performs a full RSA encryption. For another, better example, the client can xe2x80x9clightly encryptxe2x80x9d the plaintext message M, forming a ciphertext m with an algorithm that is less computationally expensive than RSA, and then securely pass the xe2x80x9clightly encryptedxe2x80x9d message m to the proxy, which in turn performs a full encryption, forming the ciphertext Mxe2x80x2. (It will be appreciated that some form of authentication would typically be used between the client and the proxy.)
The problem with these examples is the absence of end-to-end, client-server security. Indeed, the client must trust the proxy because the proxy has easy access to the plaintext M. Applicants invention achieves end-to-end, client-server security at the same time as a computationally expensive encryption algorithm is off-loaded to an untrusted proxy, i.e., without revealing the plaintext to the proxy.
General aspects of the problem of computing with encrypted data are described in B. Schneier, Applied Cryptography 2d ed., sections 4.8 and 23.6, pp. 85-86 and 540-541, John Wiley and Sons (1996). Also, the publication by Y. Desmedt et al., xe2x80x9cShared Generation of Authenticators and Signaturesxe2x80x9d, Advances in Cryotologyxe2x80x94Cryoto""91, Lecture Notes in Computer Science, vol. 537, pp. 457-469, Springer-Verlag (1991) describes group signatures, which are schemes where a given number of individuals can collectively generate a single secure signature without interaction among the individuals and without revealing the secret key to any of them.
The Charon protocol, which is described in A. Fox et al., xe2x80x9cSecurity on the Move: Indirect Authentication Using Kerberosxe2x80x9d, Proceedings Mobicom 96 (1996), provides indirect authentication using a trusted proxy for the Kerberos authentication protocol.
The Internet publication, M. Blaze et al., xe2x80x9cAtomic Proxy Cryptographyxe2x80x9d, www.research.att.com, ATandT Labsxe2x80x94Research (Feb. 23, 1998), describes atomic proxy cryptography, in which an atomic proxy function with a proxy key converts ciphertext for a key k1 into ciphertext for another key k2.
In J. Feigenbaum, xe2x80x9cEncrypting Problem Instances, or, . . . Can You Take Advantage of Someone without Having to Trust Himxe2x80x9d, Advances in Coytologyxe2x80x94Coyto""85, Lecture Notes in Computer Science, vol. 218, pp. 477-488, Springer-Verlag (1986), a method for computing with encrypted data is described, where a party A lacks the computational power to perform a calculation and lets another untrusted party B with more computing power do a partial calculation. The result of this is further used by the original party A to compute the final result using a simpler operation.
U.S. Pat. No. 5,696,823 to Blaze describes a way to use an untrusted high-bandwidth device for block symmetric encryption on behalf of a secure low-bandwidth device. PKC is used for authentication or key exchange in the symmetric cryptographic protocols, not for information data encryption. The patent is directed to symmetric encryption, not the problem of public key encryption xe2x80x9con the flyxe2x80x9d. Also, the host does not only act as a proxy; calculations made by the host must be performed if it should be possible to encrypt or decrypt a message, and the cleartext is located in the insecure device after decryption. Thus, the host is xe2x80x9cuntrustedxe2x80x9d only with respect to the secret key, not with respect to the data to be encrypted.
None of these publications solves the problem addressed by Applicants"" invention, which provides end-to-end, client-server security at the same time as a computationally expensive encryption algorithm is off-loaded to an untrusted proxy, i.e., without revealing the plaintext to the proxy.
The present invention addresses certain shortcomings in the art by providing a network architecture and method for providing secure (e.g., encrypted) communications between a client and server that enables computationally expensive encryption calculations to be performed by a proxy server, rather than by the client. In other words, the methods of the present invention enable the client to delegate certain computationally expensive encryption calculations to the proxy server. Delegating these computations is particularly advantageous for xe2x80x9cthinxe2x80x9d clients (e.g., devices which are characterized by limited processing power, transmission bandwidth, and/or memory). Delegating these computations enables a thin client to utilize more advanced encryption algorithms, thereby enhancing the security of the communications link between the client and the server.
Advantageously, the present invention enables the client to delegate computations to an untrusted proxy server. An untrusted proxy server does not have access to the data message. The use of an untrusted proxy server further enhances the security of the data transmitted between the client and the server. Further, the present invention provides a system and method for indirect encryption that effectively reduces the on-line computation time at the client required by a PKC algorithm such as RSA by using idle computing cycles of the client and by using less computing-intensive cryptographic functions.
In one aspect of the invention, a method of encrypting information includes the steps of generating a random value; computing a second value based on the random value and a publickey associated with an intended recipient of the information; masking the information with the random value based on the public key; communicating the masked information and the second value to an untrusted proxy; and encrypting the information in the untrusted proxy based on the masked information, the second value, and the public key. The method may further include the step of communicating the encrypted information to the intended recipient. The masking step may include multiplying the information by the random value.
In the context of a communications network adapted to maintain RSA public-key encrypted communications sessions between one or more servers having a public encryption key and one or more clients, another aspect of the invention provides a method of transmitting information messages between a client and a server while using the computational services of an untrusted proxy, comprising the steps of generating, in a processor located in the communications network a random value; computing, in a processor located at a client, a second value based on the random value and a public key associated with a server on the network; masking the information message with the random value; transmitting to untrusted proxy the masked information message and the second value; encrypting the masked information message in a processor at the untrusted proxy; and transmitting the encrypted information message from the untrusted proxy to the server.
In another aspect, the invention provides a communications network architecture capable of maintaining RSA public-key encrypted communications sessions between one or more servers having a public encryption key and one or more clients, comprising at least one server for maintaining communications sessions with clients, the server having at least one public encryption key associated therewith; at least one client having a processing module operational to generate a code value based on a random number and to mask an information message based upon the random number and a communications module operational to transmit the code value and the masked information message to the untrusted proxy server; and an untrusted proxy server interposed between the server and the client in the communications path and adapted to receive the code value and the masked information message from the client and to encrypt the information message for transmission to the server.